﻿#pragma once


#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<assert.h>

using namespace std;

// 颜色枚举
enum Colour
{
	RED,
	BLACK
};


template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K,V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	pair<K,V> _kv;
	Colour _col;

	RBTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};


template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:

	bool Insert(const pair<K,V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		// 不为空，插入新节点
		Node* cur = _root;
		Node* parent = nullptr;

		// 向下走
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				assert(false);
			}
		}
		// 找到该插入的位置
		cur = new Node(kv); // kv在cur位置创建节点
		cur->_col = RED; // 插入节点 红色

		// 插入位置
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		//  红黑树性质：
		//  1. 每个结点不是红色就是黑色 
		//  2. 根节点是黑色的 
		//	3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 
		//	4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点 
		//	5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点

		// 到此，插入节点父亲，也就是parent是黑色正常插入结束， 为红色，就需要一系列处理
		while (parent && parent->_col == RED)
		{
			Node* grandparent = parent->_parent;
			if (parent&& parent = grandparent->_left)
			{
				Node* uncle = grandparent->_right;

				if (uncle && uncle->_col == RED)
				{
					// 需要将parent && uncle 都变黑色，并且grandparent 变成红色
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

					// 再继续向上从grandparent处理
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{

				}

			}
		}
	}


private:
	Node* _root = nullptr;
};
